/*
* 四叉树*/
//copy from http://www.nshen.net/article/2011-08-25/as3-DataStructure/
(function(win) {
	var Rectangle = win.Rectangle = function(x, y, width, height) {
		this.x = x;
		this.y = y;
		this.width = width;
		this.height = height;
	};

	Rectangle.prototype = Object.create(null, {
		bottom: {
			get: function() {
				return this.y + this.height;
			}
		},
		right: {
			get: function() {
				return this.x + this.width;
			}
		}
	});


	var QuadTree = win.QuadTree = function(rect, maxDepth, currentDepth) {
		this._rect = rect;
		this._depth = currentDepth || 0;
		this._maxDepth = maxDepth || 3;

		this._hw = rect.width >> 1;
		this._hh = rect.height >> 1;
		this._midX = rect.x + this._hw;
		this._midY = rect.y + this._hh;

		this.clear();
	};

	QuadTree.prototype.clear = function() {
		this._children = [];
		this._topLeft = this._topRight = this._bottomLeft = this._bottomRight = null
	};

	QuadTree.prototype.toString = function() {
		var s = "[QuadTreeNode> ";
		var l = this._children.length;
		s += l > 1 ? (l + " children") : (l + " child");

		return s;
	};

	/**
	 *   节点按 <左上，右上，左下，右下>输出
	 */
	QuadTree.prototype.dump = function() {
		var s = "";
		this.preorder(this, function(node){
			var d = node._depth;
			for (var i = 0; i < d; i++) {
				if (i == d - 1)
					s += "+---";
				else
					s += "|    ";
			}
			s += node + "\n";
		});
		return s;
	};

	QuadTree.prototype.preorder = function(node, process) {
		process(node);

		if (node._topLeft) {
			this.preorder(node._topLeft, process);
		}
		if (node._topRight) {
			this.preorder(node._topRight, process);
		}
		if (node._bottomLeft) {
			this.preorder(node._bottomLeft, process);
		}
		if (node._bottomRight) {
			this.preorder(node._bottomRight, process);
		}
	};

	// obj {x:,y:,width:,height:}	
	QuadTree.prototype.retrieve = function(obj) {
		var r = [];
		if (!this._topLeft) {
			r.push.apply(r, this._children);
			return r;
		}

		//如果所取区块比本身区域还大，那么它所有子树的children都取出
		if (obj.x <= this._rect.x && obj.y <= this._rect.y && obj.x + obj.width >= this._rect.right && obj.y + obj.height >= this._rect.bottom) {
			r.push.apply(r, this._children);
			r.push.apply(r, this._topLeft.retrieve(obj));
			r.push.apply(r, this._topRight.retrieve(obj));
			r.push.apply(r, this._bottomLeft.retrieve(obj));
			r.push.apply(r, this._bottomRight.retrieve(obj));
			return r;
		}

		//否则就只取对应的区域子树
		var objRight = obj.x + obj.width;
		var objBottom = obj.y + obj.height;

		// 完全在分区里 
		if ((obj.x > this._rect.x) && (objRight < this._midX)) {
			if (obj.y > this._rect.y && objBottom < this._midY) {
				r.push.apply(r, this._topLeft.retrieve(obj));
				return r;
			}
			if (obj.y > this._midY && objBottom < this._rect.bottom) {
				r.push.apply(r, this._bottomLeft.retrieve(obj));
				return r;
			}
		}
		if (obj.x > this._midX && objRight < this._rect.right) {
			if (obj.y > this._rect.y && objBottom < this._midY) {
				r.push.apply(r, this._topRight.retrieve(obj));
				return r
			}
			if (obj.y > this._midY && objBottom < this._rect.bottom) {
				r.push.apply(r, this._bottomRight.retrieve(obj));
				return r
			}
		}

		//只要有部分在分区里，也放到对应分区里，但注意可以重复放			

		//上边
		if (objBottom > this._rect.y && obj.y < this._midY) {

			if (obj.x < this._midX && objRight > this._rect.x) {
				r.push.apply(r, this._topLeft.retrieve(obj));
			}
			if (obj.x < this._rect.right && objRight > this._midX) {
				r.push.apply(r, this._topRight.retrieve(obj));
			}
		}
		// 下边
		if (objBottom > this._midY && obj.y < this._rect.bottom) {
			if (obj.x < this._midX && objRight > this._rect.x) {
				r.push.apply(r, this._bottomLeft.retrieve(obj));
			}

			if (obj.x < this._rect.right && objRight > this._midX) {
				r.push.apply(r, this._bottomRight.retrieve(obj));
			}
		}
		return r;
	};

	// obj {x:,y:,width:,height:}	or   /*[obj, obj, obj]*/
	QuadTree.prototype.insert = function(obj) {
		/*		if (Object.prototype.toString.call(obj) === "[object Array]") {
		 for (var i = 0, l = obj.length; i < l; i++) {
		 this.insert(obj[i])
		 }
		 return;
		 }*/

		// 如果不能切分或者obj比整个区域还大，就放到children里
		if (this._depth >= this._maxDepth || (obj.x <= this._rect.x && obj.y <= this._rect.y && obj.x + obj.width >= this._rect.right && obj.y + obj.height >= this._rect.bottom)) {
			this._children.push(obj);
			return;
		}

		if (!this._topLeft) {
			var d = this._depth + 1;
			this._topLeft = new QuadTree(new Rectangle(this._rect.x, this._rect.y, this._hw, this._hh), this._maxDepth, d);
			this._topRight = new QuadTree(new Rectangle(this._rect.x + this._hw, this._rect.y, this._hw, this._hh), this._maxDepth, d);
			this._bottomLeft = new QuadTree(new Rectangle(this._rect.x, this._rect.y + this._hh, this._hw, this._hh), this._maxDepth, d);
			this._bottomRight = new QuadTree(new Rectangle(this._rect.x + this._hw, this._rect.y + this._hh, this._hw, this._hh), this._maxDepth, d);
		}

		var objRight = obj.x + obj.width;
		var objBottom = obj.y + obj.height;

		// 可以完全放到分区里就递归放到对应分区里
		if ((obj.x > this._rect.x) && (objRight < this._midX)) {
			if (obj.y > this._rect.y && objBottom < this._midY) {
				this._topLeft.insert(obj);
				return;
			}
			if (obj.y > this._midY && objBottom < this._rect.bottom) {
				this._bottomLeft.insert(obj);
				return;
			}
		}
		if (obj.x > this._midX && objRight < this._rect.right) {
			if (obj.y > this._rect.y && objBottom < this._midY) {
				this._topRight.insert(obj);
				return;
			}
			if (obj.y > this._midY && objBottom < this._rect.bottom) {
				this._bottomRight.insert(obj);
				return;
			}
		}

		//只要有部分在分区里，也放到对应分区里，但注意可以重复放			

		//上边
		if (objBottom > this._rect.y && obj.y < this._midY) {

			if (obj.x < this._midX && objRight > this._rect.x) {
				this._topLeft.insert(obj);
			}
			if (obj.x < this._rect.right && objRight > this._midX) {
				this._topRight.insert(obj);
			}
		}
		// 下边
		if (objBottom > this._midY && obj.y < this._rect.bottom) {
			if (obj.x < this._midX && objRight > this._rect.x) {
				this._bottomLeft.insert(obj);
			}

			if (obj.x < this._rect.right && objRight > this._midX) {
				this._bottomRight.insert(obj);
			}
		}
	}

})(this);